今日題目

題目連結：700. Search in a Binary Search Tree
題目主題：Tree, Binary Search Tree, Binary Tree

簡單說說 Binary Search Tree

昨天分享了 Binary Search Tree 的原則，今天來説說Binary Search Tree 是怎麼快速找到目標值的。

Binary Search Tree 的原則是越左邊的值越小、越右邊的值越大，也就是説根節點的左半部一定都小於根節點、右半部一定都大於根節點，如果要搜尋一個值，會從根節點開始走，運作過程如下圖：

範例： tree = [5, 2, 6, 1, 3, null, 8]

目標值：8

目標值大於根節點，直接往右走，走到第二層是 6 ，目標值 8 還是大於 6 ，所以繼續往右走，最終搜尋到這棵樹裡面有 8。

目標值：3

目標值小於根節點，直接往左走，走到第二層是 2 ，目標值 3 大於 2 ，所以接著往右走，最終搜尋到這棵樹裡面有 3。

目標值：10

目標值大於根節點，直接往右走，走到第二層 6 ，目標值 10 還是大於 6 ，所以繼續往右走，第三層是 8 發現 10 還是比較大，所以又往下一層右邊走，但發現已經沒有節點了，所以可以下結論這棵樹裡面沒有 10 這個值。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目會給一個Binary Search Tree及一個目標值，目標是確認這個目標值是否在這顆Binary Search Tree中，若有出現的話，回傳目標值所在的TreeNode，若沒找到回傳 Null 代表沒有。

約束：

• 這是一顆Binary Search Tree
• 樹的節點總數範圍在[1, 5000]
• 1 <= Node.val <= 10的7次方
• 1 <= val <= 10的7次方

範例1

輸入：root = [4,2,7,1,3], val = 2
輸出：[2, 1, 3]
解說：目標值 2 在 root 裡面有出現，因此回傳 2 這個TreeNode，參考上圖。

範例2

輸入：root = [4,2,7,1,3], val = 5
輸出：[]
解說：目標值 5 在 root 裡面找不到，因此回傳null

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 寫一個遞迴方法，每次使用傳進一個TreeNode及目標值。
2. 每次進入方法會檢查以下：
   • 目前是否有節點，若沒有節點代表這棵樹不存在目標值，回傳 Null 結束。
   • 目前節點的值是否與目標值相同，若相同回傳目前節點結束。
   • 目標值若小於目前節點的值，往目前節點的左邊子節點走。
   • 目標值若大於目前節點的值，往目前節點的右邊子節點走。

圖解過程

範例：root = [5, 2, 6, 1, 3, null, 8]
目標值：3

如上圖所示，目標值為 3 小於根節點的值 5 先往左走，走到第二層目標值 3 大於目前節點的值 2 ，所以接著往右走，最終搜尋到這棵樹裡面有 3 這個節點，最終回傳這個節點結束。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 若沒有節點，代表走到樹的底且目標值不在樹中
        if root == None: return None
        # 若有與目標值相同值的節點，代表找到目標回傳這個節點
        if root.val == val: return root
        
        # 若值大於目前節點的值，往下層右邊節點走
        if val > root.val:
            return self.searchBST(root.right, val)
        # 若值小於目前節點的值，往下層左邊節點走
        if val < root.val:
            return self.searchBST(root.left, val)

希望您今天能瞭解到...

1. Binary Search Tree 搜尋值
2. 700. Search in a Binary Search Tree 的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：501. Find Mode in Binary Search Tree